/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB)  return NULL;
        /*
        两个链表出现head或head->next相同的情况即为公共节点;
        使用哈希表：将其中一条链表信息存入哈希表中，在遍历第二条链表时依次查找各个链表是否在之前链表中已出现
        */
        unordered_map<ListNode *, int> um;
        ListNode * newHeadA = headA;
        while(newHeadA)
        {
            ++um[newHeadA];
            newHeadA = newHeadA->next;
        }

        unordered_map<ListNode *, int>::iterator it;
        ListNode * newHeadB = headB;
        while(newHeadB)
        {
            it = um.find(newHeadB);
            if(it != um.end())  return newHeadB;
            newHeadB = newHeadB->next;
        }

        return NULL;
    }
};

/*********************************************************************************/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB)  return NULL;
        /*
        两个链表出现head或head->next相同的情况即为公共节点;
        使用哈希表：将其中一条链表信息存入哈希表中，在遍历第二条链表时依次查找各个链表是否在之前链表中已出现;
        使用两个数组储存两个链表信息，然后倒序判断第一个公共节点
        */
        vector<ListNode *> a;
        vector<ListNode *> b;
        ListNode * newHeadA = headA;
        ListNode * newHeadB = headB;
        while(newHeadA)
        {
            a.push_back(newHeadA);
            newHeadA = newHeadA->next;
        }
        while(newHeadB)
        {
            b.push_back(newHeadB);
            newHeadB = newHeadB->next;
        }

        //倒序查找
        int a_ptr = a.size() - 1;
        int b_ptr = b.size() - 1;
        if(a[a_ptr] != b[b_ptr])  return NULL;
        while(a_ptr >= 0 && b_ptr >= 0)
        {
            if(a[a_ptr] == b[b_ptr]){
                --a_ptr;
                --b_ptr;    
            }
            else
            {
                break;
            }  
        }

        return a[a_ptr + 1];
    }
};

/******************************************************************************************************/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB)  return NULL;
        /*
        两个链表出现head或head->next相同的情况即为公共节点;
        1.使用哈希表：将其中一条链表信息存入哈希表中，在遍历第二条链表时依次查找各个链表是否在之前链表中已出现;
        2.使用两个数组储存两个链表信息，然后倒序判断第一个公共节点(或使用辅助栈);
        3.(剑指)分析两段链表特点，如果我们先让长链表先行几步，然后两个链表开始同时遍历，就能保证同时到达第一个公共节点处
        */
        int sizeOfA = 0;
        int sizeOfB = 0;
        ListNode * newHeadA = headA;
        ListNode * newHeadB = headB;
        while(newHeadA)
        {
            ++sizeOfA;
            newHeadA = newHeadA->next;
        }
        while(newHeadB)
        {
            ++sizeOfB;
            newHeadB = newHeadB->next;
        }

        ListNode * front = (sizeOfA >= sizeOfB) ? headA : headB;
        ListNode * end = (sizeOfA >= sizeOfB) ? headB : headA;

        int number = abs(sizeOfA - sizeOfB);

        while(number > 0 && front)
        {
            front = front->next;
            --number;
        }

        while(front && end)
        {
            if(front == end) break;
            front = front->next;
            end = end->next;
        }

        return front;
    }
};